package vernhe;

import java.util.Comparator;

/**
 * AVL树
 * @param <E>
 */
public class AVLTree<E> extends BBST<E>{
    public AVLTree() {
        this(null);
    }

    public AVLTree(Comparator<E> comparator) {
        super(comparator);
    }

    /**
     * 添加新节点后的处理
     * @param node 新添加的节点
     */
    @Override
    protected void addAfter(Node<E> node) {
        //查找新添加节点的parent，寻找第一个失衡节点
        while ((node = node.parent) != null) {
            if (isBalanced(node)) {
                //如果新添加节点的某个父节点是平衡状态，就更新它的高度
                updateHeight(node);
            }else {
                //找到第一个不平衡的父节点，使其恢复平衡
                rebalance(node);
                break;
            }
        }
    }

    /**
     * 删除节点之后的操作
     * @param node 刚被删除的节点
     */
    @Override
    protected void afterRemove(Node<E> node) {
        while ((node = node.parent) != null) {
            if (isBalanced(node)) {
                //如果新添加节点的某个父节点是平衡状态，就更新它的高度
                updateHeight(node);
            }else {
                //需要一直往上找，直至所有祖先节点都不失衡
                rebalance(node);
            }
        }
    }

    /**
     * 对子类提供一个创建节点的接口
     * @param element
     * @param parent
     * @return
     */
    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode<>(element,parent);
    }

    /**
     * 恢复平衡
     * @param grand 高度最低的不平衡节点
     */
    private void rebalance2(Node<E> grand) {
        //找到parent 和 node
        Node<E> parent = ((AVLNode<E>)grand).tallerChild();
        Node<E> node = ((AVLNode<E>)parent).tallerChild();
        //判断是LR/RR/LR/RL中的哪一种
        if (parent.isLeft()) {  //L
            if (node.isLeft()) {    //LL
                rotateRight(grand);
            }else { //LR
                rotateLeft(parent);
                rotateRight(grand);
            }
        }else { //R
            if (node.isLeft()) {   //RL
                rotateRight(parent);
                rotateLeft(grand);
            }else { //RR
                rotateLeft(grand);
            }
        }
    }

    @Override
    protected void rotate(Node<E> r, Node<E> a, Node<E> b, Node<E> c, Node<E> d, Node<E> e, Node<E> f, Node<E> g) {
        super.rotate(r, a, b, c, d, e, f, g);
        //b的左右子树发生变化，跟新高度
        updateHeight(b);
        //f的左右子树发生变化，跟新高度
        updateHeight(f);
        //d的左右子树发生变化，跟新高度
        updateHeight(d);
    }

    @Override
    protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        super.afterRotate(grand, parent, child);
        //重新计算高度
        updateHeight(grand);
        updateHeight(parent);
    }

    private void rebalance(Node<E> grand) {
        //找到parent 和 node
        Node<E> parent = ((AVLNode<E>)grand).tallerChild();
        Node<E> node = ((AVLNode<E>)parent).tallerChild();
        //判断是LR/RR/LR/RL中的哪一种
        if (parent.isLeft()) {  //L
            if (node.isLeft()) {    //LL
                rotate(grand,node.left,node,node.right,parent,parent.right,grand,grand.right);
            }else { //LR
                rotate(grand,parent.left,parent,node.left,node,node.right,grand,grand.right);
            }
        }else { //R
            if (node.isLeft()) {   //RL
                rotate(grand,grand.left,grand,node.left,node,node.right,parent,parent.right);
            }else { //RR
                rotate(grand,grand.left,grand,parent.left,parent,node.left,node,node.right);
            }
        }
    }

    /**
     * 判断该节点是否平衡
     * @param node
     * @return
     */
    private boolean isBalanced(Node<E> node) {
        return Math.abs(((AVLNode<E>)node).balanceFactor()) <= 1;
    }

    /**
     * 跟新节点的高度
     * @param node
     */
    private void updateHeight(Node<E> node) {
        ((AVLNode<E>)node).updateHeight();
    }

    /**
     * AVL树的节点
     * @param <E>
     */
    private static class AVLNode<E> extends Node<E> {
        //新添加的节点一定是叶子节点，所以高度是1
        int height = 1;
        public AVLNode(E element, Node<E> parent) {
            super(element, parent);
        }

        /**
         * 得到该节点的平衡因子
         * @return
         */
        public int balanceFactor() {
            //默认是普通的节点，没有height属性，所以要进行强转
            int leftHeight = (left == null) ? 0 : ((AVLNode<E>)left).height;
            int rightHeight = (right == null) ? 0 : ((AVLNode<E>)right).height;
            return leftHeight - rightHeight;
        }

        /**
         * 跟新当前节点的高度
         */
        public void updateHeight() {
            int leftHeight = (left == null) ? 0 : ((AVLNode<E>)left).height;
            int rightHeight = (right == null) ? 0 : ((AVLNode<E>)right).height;
            height = 1 + Math.max(leftHeight,rightHeight);
        }

        public Node<E> tallerChild() {
            int leftHeight = (left == null) ? 0 : ((AVLNode<E>)left).height;
            int rightHeight = (right == null) ? 0 : ((AVLNode<E>)right).height;
            //返回左右节点中高度比较高的节点
            if (leftHeight > rightHeight) return left;
            if (leftHeight < rightHeight) return right;
            //如果高度一样就返回与自己同方向的节点，如果自己是父节点的左子树，就返回自己的左子树
            return isLeaf() ? left : right;
        }
    }

    @Override
    protected String toString(Node<E> node, StringBuilder sb, String perfix) {
        AVLNode avlNode = (AVLNode) node;
        if (avlNode.left != null) toString(avlNode.left,sb,perfix + "[L]");
        sb.append(perfix).append("【").append(avlNode.element).append("_h:").append(avlNode.height).append("】").append("\n");
        if (avlNode.right != null) toString(avlNode.right,sb,perfix + "[R]");
        return sb.toString();
    }
}
